#include <stdio.h>
#include <stdlib.h>

typedef int DataType;

typedef struct LNode
{
    DataType val;
    struct LNode* next;
}LNode;

void Push(LNode** head, DataType x)
{
    LNode* tmp = (LNode*)malloc(sizeof(LNode));
    if (tmp == NULL)
    {
        return;
    }
    tmp->next = NULL;
    tmp->val = x;
    if (*head == NULL)
    {
        *head = tmp;
    }
    else
    {
        LNode* next = *head;
        while (next->next)
        {
            next = next->next;
        }
        next->next = tmp;
    }
}

void DestroyNode(LNode** head)
{
    LNode* next = (*head)->next;
    while (next)
    {
        free(*head);
        *head = next;
        next = next->next;
    }
    free(*head);
}

void Print(LNode* head)
{
    while (head)
    {
        printf("%d ", head->val);
        head = head->next;
    }
}

void reverseBetween(struct LNode* head, int left, int right) {
    struct LNode* cur1 = head;
    struct LNode* cur2 = head;

    int tmpleft = left;
    int tmpright = right;
    while (--tmpleft)
    {
        cur1 = cur1->next;
    }
    while (--tmpright)
    {
        cur2 = cur2->next;
    }

    while (left < right)
    {
        int tmpval = cur1->val;
        cur1->val = cur2->val;
        cur2->val = tmpval;

        cur1 = cur1->next;
        cur2 = cur2->next;

        ++left;
        --right;
    }
}


int main() {
    LNode* L1 = NULL;

    Push(&L1, 1);
    Push(&L1, 2);
    Push(&L1, 3);
    Push(&L1, 4);
    Push(&L1, 5);

    reverseBetween(L1, 2, 4);


    DestroyNode(&L1);



    return 0;
}